import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author LKQ
 * @date 2022/2/18 20:32
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] pre = {{1,0}, {0, 1}, {0, 2}};
        solution.canFinish(2, pre);
    }
    /**
     * 存储有向图
     */
    List<Integer>[] edges;
    /**
     * 存储每个节点的入度
     */
    int[] in;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new List[numCourses];
        for (int i = 0; i < numCourses; ++i) {
            edges[i] = new ArrayList<Integer>();
        }
        in = new int[numCourses];
        for (int[] info : prerequisites) {
            edges[info[1]].add(info[0]);
            ++in[info[0]];
        }
        Queue<Integer> queue = new LinkedList<Integer>();
        // 将所有入度为 0 的节点放入队列中
        for (int i = 0; i < numCourses; ++i) {
            if (in[i] == 0) {
                queue.offer(i);
            }
        }
        int cnt = 0;
        while (!queue.isEmpty()) {
            // 从队首取出一个节点
            int u = queue.poll();
            cnt++;
            for (int v: edges[u]) {
                --in[v];
                // 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了
                if (in[v] == 0) {
                    queue.offer(v);
                }
            }
        }
        return cnt == numCourses;
    }
}
